package other;

public class L148 {
    //给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
//
//
//
//
//
//
// 示例 1：
//
//
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
//
//
// 示例 2：
//
//
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
//
//
// 示例 3：
//
//
//输入：head = []
//输出：[]
//
//
//
//
// 提示：
//
//
// 链表中节点的数目在范围 [0, 5 * 10⁴] 内
// -10⁵ <= Node.val <= 10⁵
//
//
//
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
// Related Topics 链表 双指针 分治 排序 归并排序 👍 1694 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    //    public void sort()
    public static void main(String[] args) {
        ListNode listNode=new ListNode(4);
        ListNode listNode1=new ListNode(2);
        listNode.next=listNode1;
        ListNode listNode2=new ListNode(1);
        listNode1.next=listNode2;
        ListNode listNode3=new ListNode(3);
        listNode2.next=listNode3;
        ListNode res = sortList(listNode);
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //nlogn的时间复杂度 单项链表适合 归并排序，双向链表适合 快排
        ListNode pre = new ListNode();
        //借助快慢指针 寻找中间节点
        ListNode slow = head;  //slow最终为中间节点
        ListNode quick = head;

        while (quick.next != null) {
            quick = quick.next.next;
            slow = slow.next;
            if (quick == null) {
                break;
            }
        }
        ListNode l = head;
        ListNode r = slow;
        ListNode ptr = pre;
        while (true) {
            if (l != slow && r != null) {
                if (l.val <= r.val) {
                    ptr.next = l;
                    l = l.next;
                } else {
                    ptr.next = r;
                    r = r.next;
                }
                ptr = ptr.next;
            } else if (l == slow) {
                ptr.next = r;
            } else {
                ptr.next = l;
                while (l.next != slow) {
                    l = l.next;
                }
                l.next = null;
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
